#include<iostream>
#include<vector>
#include<deque>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    private:
    vector<vector<int>> ret;

    public:
    vector<vector<int>> ans1(int n, int k){
        vector<int> temp, nums;
        for(int i = 1; i != n+1; i++){
            nums.push_back(i);
        }
        add(0, temp, nums, k);

        return ret;
    }

    void add(int left, vector<int>& temp, vector<int> nums, int k){
        if(temp.size() == k){
            ret.push_back(temp);
        }else{
            for(int i = left; i != nums.size(); i++){
                temp.push_back(nums[i]);
                add(i+1, temp, nums, k);
                temp.pop_back();
            }
        }
    }

};

void test(){
    Solution s;
    int n = 4, k = 2;

    vector<vector<int>> ret = s.ans1(n, k);
    for(int i = 0; i != ret.size(); i++){
        for(int j = 0; j != ret[0].size()-1; j++){
            cout << ret[i][j] << " " << ends;
        }
        cout << ret[i][ret[0].size()-1] << endl;
    }
}

int main(void){
    test();

    return 0;
}